﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;

namespace Mindless
{
    /// <summary>
    /// A linear probe hash table has the advantage of (almost) never allocating memory, so it's
    /// good for quieting the garbage collector. Note that the default value for the key class is
    /// used to indicate an "empty" location, so this key can never actually be stored in the
    /// dictionary.
    /// </summary>
    class LinearProbeDictionary<TKey, TValue> : IDictionary<TKey, TValue>
        where TKey : IDoubleHash, IEquatable<TKey>
    {
        /// <summary>
        /// The dictionary consists of an array of pairs (no "buckets").
        /// </summary>
        BigArray<KeyValuePair<TKey, TValue>> pairs;

        /// <summary>
        /// Number of items in the dictionary.
        /// </summary>
        int count = 0;

        /// <summary>
        /// Number of elements the dictionary can hold without reallocating memory.
        /// </summary>
        int capacity;

        /// <summary>
        /// Constructs a dictionary that can contain the given number of elements without
        /// allocating any additional memory.
        /// </summary>
        public LinearProbeDictionary(int capacity)
        {
            this.capacity = capacity;

                // linear probe algorithm requires extra space in order to perform adequately
            int nPairs = (int) (1.5 * this.capacity);   // try to avoid overflow here
            this.pairs = new BigArray<KeyValuePair<TKey, TValue>>(nPairs);
        }

        /// <summary>
        /// Increments the receiver's count by one, and grows the receiver's capacity if necessary.
        /// </summary>
        void IncrementCount()
        {
            this.count += 1;

                // note that this occurs long before the "pairs" array is completely full
            if (this.count > this.capacity)
            {
                    // copy to a new dictionary with 2x capacity
                LinearProbeDictionary<TKey, TValue> larger = new LinearProbeDictionary<TKey, TValue>(2 * this.capacity);
                foreach (KeyValuePair<TKey, TValue> pair in this)
                    larger.Add(pair);

                    // steal the new dictionary's internal data structures
                this.pairs = larger.pairs;
                this.count = larger.count;
                this.capacity = larger.capacity;
            }
        }

        /// <summary>
        /// Finds and answers the index of the given key within the receiver. If the key is not found, the index
        /// where it should be inserted is answered.
        /// </summary>
        KeyValuePair<int /*index*/, bool /*found*/> IndexOf(TKey key)
        {
                // use first hash code to determine starting index for search
            int iPair = key.GetHashCode() % this.pairs.Length;

                // use second hash code to determine search increment (see Sedgewick)
            int inc = key.GetHashCode2();

            bool found = false;
            KeyValuePair<TKey, TValue> pair;
            while (true)
            {
                pair = this.pairs[iPair];

                    // we found the key?
                if (pair.Key.Equals(key))
                {
                    found = true;
                    break;
                }
                    // we have to stop because we found an empty slot?
                else if (pair.Key.Equals(default(TKey)))
                    break;

                    // skip to next slot
                iPair = (iPair + inc) % this.pairs.Length;
            }

            return new KeyValuePair<int, bool>(iPair, found);
        }

        #region IDictionary<TKey,TValue> Members

        /// <summary>
        /// Adds the given value with the given key to the receiver.
        /// </summary>
        public void Add(TKey key, TValue value)
        {
            this.Add(new KeyValuePair<TKey, TValue>(key, value));
        }

        /// <summary>
        /// Indicates whether the receiver contains the given key.
        /// </summary>
        public bool ContainsKey(TKey key)
        {
            return this.IndexOf(key).Value;
        }

        /// <summary>
        /// Answers the receiver's keys.
        /// </summary>
        public ICollection<TKey> Keys
        {
            get
            {
                IList<TKey> keys = new List<TKey>(this.Count);
                foreach (KeyValuePair<TKey, TValue> pair in this.pairs)
                {
                    if (!pair.Key.Equals(default(TKey)))
                        keys.Add(pair.Key);
                }

                return keys;
            }
        }

        /// <summary>
        /// Removes the given key from the receiver. Not currently implemented, since this
        /// requires a second "special" value in addition to default(TKey).
        /// </summary>
        public bool Remove(TKey key)
        {
            throw new NotImplementedException();
        }

        /// <summary>
        /// Indicates whether the given key is present in the receiver and answers the corresponding
        /// value if so.
        /// </summary>
        public bool TryGetValue(TKey key, out TValue value)
        {
            KeyValuePair<int, bool> index = this.IndexOf(key);
            value = this.pairs[index.Key].Value;

            return index.Value;
        }

        /// <summary>
        /// Answers the receiver's values.
        /// </summary>
        public ICollection<TValue> Values
        {
            get
            {
                IList<TValue> values = new List<TValue>(this.Count);
                foreach (KeyValuePair<TKey, TValue> pair in this.pairs)
                {
                    if (!pair.Key.Equals(default(TKey)))
                        values.Add(pair.Value);
                }

                return values;
            }
        }

        /// <summary>
        /// Accesses the item with the given key.
        /// </summary>
        public TValue this[TKey key]
        {
            get
            {
                KeyValuePair<int, bool> index = this.IndexOf(key);
                if (!index.Value)
                    throw new KeyNotFoundException(key.ToString());

                return this.pairs[index.Key].Value;
            }
            set
            {
                Debug.Assert(!key.Equals(default(TKey)));

                    // overwrite the current item with this key if it is present
                KeyValuePair<int, bool> index = this.IndexOf(key);
                this.pairs[index.Key] = new KeyValuePair<TKey, TValue>(key, value);

                    // if there was no existing item with this key, increment the receiver's count
                if (!index.Value)
                    this.IncrementCount();
            }
        }

        #endregion

        #region ICollection<KeyValuePair<TKey,TValue>> Members

        /// <summary>
        /// Adds the given key/value pair to the receiver.
        /// </summary>
        public void Add(KeyValuePair<TKey, TValue> pair)
        {
            Debug.Assert(!pair.Key.Equals(default(TKey)));

            KeyValuePair<int, bool> index = this.IndexOf(pair.Key);
            if (index.Value)
                throw new ArgumentException(string.Format("An item with the same key already exists in the dictionary: {0}", pair.Key));

            this.pairs[index.Key] = pair;
            this.IncrementCount();
        }

        /// <summary>
        /// Resets the receiver so that it contains no items.
        /// </summary>
        public void Clear()
        {
            this.pairs.Initialize();
            this.count = 0;
        }

        /// <summary>
        /// Indicates whether the receiver contains the given pair.
        /// </summary>
        public bool Contains(KeyValuePair<TKey, TValue> pair)
        {
            KeyValuePair<int, bool> index = this.IndexOf(pair.Key);

            return index.Value ? this.pairs[index.Key].Value.Equals(pair.Value) : false;
        }

        /// <summary>
        /// Copies the receiver's items to the given array.
        /// </summary>
        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            List<KeyValuePair<TKey, TValue>> pairs = new List<KeyValuePair<TKey, TValue>>(this);
            pairs.CopyTo(array, arrayIndex);
        }

        /// <summary>
        /// Answers the number of items in the receiver.
        /// </summary>
        public int Count
        {
            get { return this.count; }
        }

        /// <summary>
        /// Indicates whether the receiver is read-only.
        /// </summary>
        public bool IsReadOnly
        {
            get { return false; }
        }

        /// <summary>
        /// Removes the given item from the receiver.
        /// </summary>
        public bool Remove(KeyValuePair<TKey, TValue> item)
        {
            throw new NotImplementedException();
        }

        #endregion

        #region IEnumerable<KeyValuePair<TKey,TValue>> Members

        /// <summary>
        /// Enumerates the receiver's items.
        /// </summary>
        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
                // enumerate the non-default pairs
            foreach (KeyValuePair<TKey, TValue> pair in this.pairs)
            {
                if (!pair.Key.Equals(default(TKey)))
                    yield return pair;
            }
        }

        #endregion

        #region IEnumerable Members

        /// <summary>
        /// Enumerates the receiver's items.
        /// </summary>
        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        #endregion
    }

    /// <summary>
    /// Second hash code improves performance of linear probe hash table.
    /// </summary>
    interface IDoubleHash
    {
        int GetHashCode2();
    }
}
